import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list=new ArrayList<>();
        int i=0;
        for (;i<intervals.length;i++) {
            int[] interval=intervals[i];
            if (interval[1]<newInterval[0]){
                list.add(interval);
            }else {
                break;
            }
        }
        if (intervals.length==i){
            list.add(newInterval);
            return deal(list);
        }
        int left=Math.min(newInterval[0],intervals[i][0]);
        int last=i;
        for (;i<intervals.length;i++){
            if (intervals[i][0]>newInterval[1]){
                break;
            }
        }
        int right;
        if (last==i){
            right=newInterval[1];
        }else{
            right=Math.max(intervals[i-1][1],newInterval[1]);
        }
        list.add(new int[]{left,right});
        for (;i<intervals.length;i++){
            list.add(intervals[i]);
        }
        return deal(list);
    }

    private int[][] deal(List<int[]> list) {
        int[][] ans=new int[list.size()][2];
        for (int i=0;i<list.size();i++){
            ans[i]=list.get(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] ans=new Solution57().insert(new int[][]{{1,2},{3,5},{6,7},{8,10},{12,16}},new int[]{4,5});
        for (int[] an : ans) {
            System.out.println(Arrays.toString(an));
        }
    }
}
